#include <iostream>//牛客网——dp42，完全背包
#include <vector>
using namespace std;

int main() {
    int n=0,V=0;
    cin>>n>>V;
    vector<int> w(n);
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i]>>w[i];
    }
    vector<vector<int>> dp(n+1,vector<int>(V+1));

    for(int i=1;i<n+1;i++){
        for(int j=1;j<V+1;j++){
            dp[i][j]=dp[i-1][j];
            if(j-v[i-1]>=0) dp[i][j]=max(dp[i][j],dp[i][j-v[i-1]]+w[i-1]);
        }
    }

    cout<<dp[n][V]<<endl;
    dp.assign(n+1,vector<int>(V+1));
    for(int j=1;j<V+1;j++) dp[0][j]=-1;
    for(int i=1;i<n+1;i++){
        for(int j=1;j<V+1;j++){
            dp[i][j]=dp[i-1][j];
            if(j-v[i-1]>=0&&dp[i][j-v[i-1]]!=-1) dp[i][j]=max(dp[i-1][j],dp[i][j-v[i-1]]+w[i-1]);
        }
    }
    cout<<(dp[n][V]==-1?0:dp[n][V])<<endl;
    return 0;
}